﻿#region Copyright (c) 2003 - 2008, Andreas Mueller
/////////////////////////////////////////////////////////////////////////////////////////
// 
// Copyright (c) 2003 - 2008, Andreas Mueller.
// All rights reserved. This program and the accompanying materials
// are made available under the terms of the Eclipse Public License v1.0
// which accompanies this distribution, and is available at
// http://www.eclipse.org/legal/epl-v10.html
//
// Contributors:
//    Andreas Mueller - initial API and implementation
//
// 
// This software is derived from software bearing the following
// restrictions:
// 
// Copyright (c) 1994
// Hewlett-Packard Company
// 
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Hewlett-Packard Company makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
// 
// 
// Copyright (c) 1996,1997
// Silicon Graphics Computer Systems, Inc.
// 
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Silicon Graphics makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
// 
// 
// (C) Copyright Nicolai M. Josuttis 1999.
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all copies.
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
// 
/////////////////////////////////////////////////////////////////////////////////////////
#endregion

using System;
using System.Collections.Generic;
using NStl.Iterators.Support;
using NStl.Linq;
using NStl.NUnit.AlgorithmFixtures.TopologicalSort;
using NUnit.Framework;
using NUnit.Framework.SyntaxHelpers;
using Rhino.Mocks;

namespace NStl.NUnit.AlgorithmFixtures.TopologicalSort
{
    [TestFixture]
    public class TopologicalSortFixture : AlgorithmBaseFixture
    {
        [Test]
        public override void SuccessfullPass()
        {
            IGraphNode a = mockRepository.Stub<IGraphNode>();
            IGraphNode b = mockRepository.Stub<IGraphNode>();
            IGraphNode c = mockRepository.Stub<IGraphNode>();
            IGraphNode d = mockRepository.Stub<IGraphNode>();
            IGraphNode e = mockRepository.Stub<IGraphNode>();

            using (mockRepository.Record())
            {
                Expect.Call(a.Parents).Return(new IGraphNode[] { }).Repeat.Any();

                Expect.Call(b.Parents).Return(new[] { a }).Repeat.Any();
                Expect.Call(c.Parents).Return(new[] { a }).Repeat.Any();

                Expect.Call(d.Parents).Return(new[] { b }).Repeat.Any();
                Expect.Call(e.Parents).Return(new[] { b, c }).Repeat.Any();
            }

            IGraphNode[] graph = ShuffledGraph(a, b, c, d, e);

            List<IGraphNode> sortedGraph = new List<IGraphNode> { null, null, null, null, null, null, null, null};

            ListTIterator<IGraphNode> targetEnd =  
                Algorithm.TopologicalSort(graph.Begin(), graph.End(), sortedGraph.Begin(), Functional.PtrFun<IGraphNode, IEnumerable<IGraphNode>>(node => node.Parents));

            IRange<IGraphNode> actual = sortedGraph.Begin().AsRange(targetEnd);

            Assert.That(actual, Iz.EquivalentTo(graph));

            bool isSorted = TopologicalSortSupportFixture.IsTopologicallySorted(actual, node => node.Parents);
            Assert.That(isSorted, Iz.True);
        }
        [Test]
        public override void NonSuccessfullPass()
        {
            IGraphNode a = mockRepository.Stub<IGraphNode>();
            IGraphNode b = mockRepository.Stub<IGraphNode>();
            IGraphNode c = mockRepository.Stub<IGraphNode>();

            using (mockRepository.Record())
            {
                Expect.Call(a.Parents).Return(new IGraphNode[] { }).Repeat.Any();

                Expect.Call(b.Parents).Return(new IGraphNode[] { }).Repeat.Any();
                Expect.Call(c.Parents).Return(new IGraphNode[] { }).Repeat.Any();

            }

            IGraphNode[] graph = ShuffledGraph(a, b, c);

            List<IGraphNode> sortedGraph = new List<IGraphNode> { null, null, null, null, null, null, null, null };

            ListTIterator<IGraphNode> targetEnd =
                Algorithm.TopologicalSort(graph.Begin(), graph.End(), sortedGraph.Begin(), Functional.PtrFun<IGraphNode, IEnumerable<IGraphNode>>(node => node.Parents));

            IRange<IGraphNode> actual = sortedGraph.Begin().AsRange(targetEnd);

            Assert.That(actual, Iz.EqualTo(graph));
        }
        [Test]
        public override void StartIteratorIsEqualToEndIterator()
        {
            IGraphNode a = mockRepository.Stub<IGraphNode>();
            IGraphNode b = mockRepository.Stub<IGraphNode>();
            IGraphNode c = mockRepository.Stub<IGraphNode>();

            using (mockRepository.Record())
            {
                Expect.Call(a.Parents).Return(new IGraphNode[] { }).Repeat.Any();

                Expect.Call(b.Parents).Return(new[] { a }).Repeat.Any();
                Expect.Call(c.Parents).Return(new[] { a }).Repeat.Any();
            }

            IGraphNode[] graph = ShuffledGraph(a, b, c);

            List<IGraphNode> sortedGraph = new List<IGraphNode> { null, null, null, null, null, null, null, null };

            ListTIterator<IGraphNode> targetEnd =
                Algorithm.TopologicalSort(graph.Begin(), graph.Begin(), sortedGraph.Begin(), Functional.PtrFun<IGraphNode, IEnumerable<IGraphNode>>(node => node.Parents));

            IRange<IGraphNode> actual = sortedGraph.Begin().AsRange(targetEnd);

            Assert.That(actual, Iz.Empty);
        }
        [Test]
        [ExpectedException(typeof(ArgumentException))]
        public void CyclicGraphThrowsArgumentException()
        {
            IGraphNode a = mockRepository.Stub<IGraphNode>();
            IGraphNode b = mockRepository.Stub<IGraphNode>();
            IGraphNode c = mockRepository.Stub<IGraphNode>();

            using (mockRepository.Record())
            {
                Expect.Call(a.Parents).Return(new[] { c }).Repeat.Any();

                Expect.Call(b.Parents).Return(new[] { a }).Repeat.Any();
                Expect.Call(c.Parents).Return(new[] { b }).Repeat.Any();
            }

            IEnumerable<IGraphNode> graph = ShuffledGraph(a, b, c);
            List<IGraphNode> sortedGraph = new List<IGraphNode> { null, null, null, null, null, null, null, null };

            Algorithm.TopologicalSort(graph.Begin(), graph.End(), sortedGraph.Begin(), Functional.PtrFun<IGraphNode, IEnumerable<IGraphNode>>(node => node.Parents));
        }
        private static T[] ShuffledGraph<T>(params T[] list)
        {
            Algorithm.RandomShuffle(list.Begin(), list.End());
            return list;
        }

        private static MockRepository mockRepository;
        [SetUp]
        public void SetUp()
        {
            mockRepository = new MockRepository();
        }
        [TearDown]
        public void TearDown()
        {
            mockRepository.VerifyAll();
        }
    }
}